package org.zjt.algorithm;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树：深度遍历、广度遍历、最大深度、前序
 *
 * 1、深度   栈区
 * 2、广度   队列
 * 3、前序   直接输出
 * 4、二叉树转为双向链表
 *
 */
public class BinaryTree {

    public static class Node {
        private Node right;
        private Node left;
        private Integer val;

        public Node(Integer val) {
            this.val = val;
        }

        public Node() {
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Integer getVal() {
            return val;
        }

        public void setVal(Integer val) {
            this.val = val;
        }
    }

    public static int maxDeep(Node node) {
        if (node == null){
            return 0;
        }
        return 1 + Math.max(maxDeep(node.left),maxDeep(node.right));
    }

    public static void deepShow(Node node) {
        Stack<Node> stack = new Stack();
        if(node != null){
            stack.push(node);
        }
        while (!stack.empty()){
            Node tmp = stack.pop();
            System.out.println(tmp.val);
            if(tmp.left != null){
                stack.push(tmp.left);
            }

            if(tmp.right != null){
                stack.push(tmp.right);
            }

        }
    }

    public static void wideShow(Node node) {
        ArrayDeque<Node> queue = new ArrayDeque<>();
        if(node != null){
            queue.push(node);
        }
        while (!queue.isEmpty()){
            Node tmp = queue.pop();
            System.out.println(tmp.val);
            if(tmp.left != null){
                queue.push(tmp.left);
            }

            if(tmp.right != null){
                queue.push(tmp.right);
            }

        }
    }

    public static void midShow(Node node) {
        if(node == null){
            return;
        }
        midShow(node.left);
        System.out.println(node.val);
        midShow(node.right);
    }

    public static void main(String[] args) {
        Node head = new Node(150);
        head.left = new Node(100);
        head.right = new Node(190);
        head.left.left= new Node(90);


        head.left.left.left= new Node(50);
        head.left.left.right= new Node(93);
       // System.out.println(maxDeep(head));
       // deepShow(head);
        inOrderBSTree(head);
        Node node = pHead;
        while (node != null){
            System.out.println(node.val);
            node = node.right;
        }
    }


    public static Node midShow2(Node node) {
        if(node == null){
            return null;
        }

        node.right = midShow2(node.right);
        return node;
    }


    //双向链表头结点（左节点）
    private static Node pHead = null;

    //双向链表尾结点（当前节点）
    private static Node pEnd = null;

    public static void inOrderBSTree(Node root){
        if(root == null){
            return;
        }
        //转换root的左子树
        inOrderBSTree(root.left);

        //双向链表为空，当前遍历的结点为双向链表的头结点
        if(pHead == null){
            pHead = root;
        }

        //上一个遍历的root节点为左下节点
        //使当前结点的左孩子指向双向链表中最后一个结点,指向左下子节点。
        root.left = pEnd;

        //使双向链表中最后一个结点的右孩子指向当前结点,上一个左子节点指向当前。
        if(pEnd != null) {
            pEnd.right = root;
        }

        //将当前结点设为双向链表中最后一个结点
        pEnd = root;

        //转换root的右子树
        inOrderBSTree(root.right);
    }

}
